package leetcode_周赛._2021._202105._20210502;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/2 10:38
 * 将字符串拆分为递减的连续值
 * 1、拆分成的数字降序
 * 2、相邻的数字之间的差值为 1
 * 使用回溯
 * 一个一个拆
 * 数字字符串太长会出现转化问题，所以只能使用字符串来比较
 *
 */
public class _5747 {
    public static void main(String[] args) {
        System.out.println(new _5747().splitString("200100"));
        System.out.println(new _5747().splitString("1234"));
        System.out.println(new _5747().splitString("050043"));
        System.out.println(new _5747().splitString("9080701"));
        System.out.println(new _5747().splitString("10009998"));
    }

    public boolean splitString(String s) {
        return dfs(s, 0, "false", 0);
    }
    public boolean dfs(String s, int start, String target, int num) {
        if ("-1".equals(target) && start != s.length()) return false;
        if (start == s.length() && num > 1) return true;
        StringBuilder cur = new StringBuilder();
        for (int i = start; i < s.length(); i++) {
            cur.append(s.charAt(i));
            if ("false".equals(target) || deleteZero(cur.toString()).equals(target)) {
                boolean flag = dfs(s, i + 1, substract(cur.toString()), num + 1);
                if (flag) return true;
            }
        }
        return false;
    }
    public String deleteZero(String s) {
        int index = s.length();
        for (int i = 0; i < s.length(); i++)
            if (s.charAt(i) != '0') {
                index = i;
                break;
            }
        return s.substring(index);
    }
    // 字符串数字减一
    // 先删除字符串中的 0
    public String substract(String s) {
        String cur = deleteZero(s);
        if (0 == cur.length()) return "-1";
        StringBuilder ans = new StringBuilder();
        char[] chars = cur.toCharArray();
        int flag = -1;
        for (int i = chars.length - 1; i >= 0; i--) {
            int tmp = Integer.parseInt(chars[i] + "") + flag;
            String c = "";
            if (tmp < 0) c = "9";
            else {
                flag = 0;
                c = tmp + "";
            }
            ans.append(c);
        }
        return deleteZero(ans.reverse().toString());
    }

}
